import com.sun.javafx.scene.control.skin.SpinnerSkin;
import sun.security.x509.IPAddressName;

import java.util.*;

public class project {




Arrays




    public static void main(String[] args) {
//        int[] arr1={1,2,3,4,5,6,7,8,9};
//        int[] arr2={9,8,7,6,5,4,3,2,1};
        int[] arr={9,8,7,6,5,4,3,2,1};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));




//        int[] arr=new int[arr1.length+arr2.length+1];
//        arr=mergeArray(arr1,arr2);
//        quickSort3(arr);
//        for(int a :mergeArray(arr1,arr2)){
//            System.out.print(a+" ");
//        }
    }


    public static void merge1(int[] arr,int gap){
        int[] tmp=new int[arr.length];
        int k=0;
        int s1=0;
        int e1=s1+gap-1;
        int s2=e1+1;
        int e2=Math.min(s2+gap-1,arr.length-1);
        while(s2<arr.length){
            while(s1<=e1&&s2<=e2){
                if(arr[s1]<=arr[s2]){
                    tmp[k++]=arr[s1++];
                }else{
                    tmp[k++]=arr[s2++];
                }
            }
            while(s1<=e1){
                tmp[k++]=arr[s1++];
            }
            while(s2<=e2){
                tmp[k++]=arr[s2++];
            }
            s1=e2+1;
            e1=s1+gap-1;
            s2=e1+1;
            e2=Math.min(s2+gap-1,arr.length-1);
        }
        while(s1<=arr.length-1){
            tmp[k++]=arr[s1++];
        }
        for(int i=0;i<k;i++){
            arr[i]=tmp[i];
        }
    }
    public static void mergeSort(int[] arr){
        for(int gap=1;gap<arr.length;gap*=2){
            merge1(arr,gap);
        }
    }








    public static void merge(int[] arr,int left,int right,int mid){
        int k=0;
        int[] tmp=new int[right-left+1];
        int i=left;
        int j=mid+1;
        while(i<=mid&&j<=right){
            if(arr[i]<=arr[j]){
                tmp[k++]=arr[i++];
            }else{
                tmp[k++]=arr[j++];
            }
        }
        while(i<=mid){
            tmp[k++]=arr[i++];
        }
        while(j<=right){
            tmp[k++]=arr[j++];
        }
        for(int p=0;p<k;p++){
            arr[p+left]=tmp[p];
        }
    }
    public static void mergeSortInternal(int[] arr,int left,int right){
        if(left>=right){
            return;
        }
        int mid=(left+right)/2;
        mergeSortInternal(arr,left,mid);
        mergeSortInternal(arr,mid+1,right);
        merge(arr,left,right,mid);
    }







    public static int[] mergeArray(int[] arr1,int[] arr2){
//        if(arr1==null&&arr2==null){
//            return null;
//        }
//        if(arr1==null){
//            return arr2;
//        }
//        if(arr2==null){
//            return arr1;
//        }
        int[] arr=new int[arr1.length+arr2.length];
        int i=0;
        int j=0;
        int k=0;
        while(i<arr1.length&&j<arr2.length){
            if(arr1[i]<=arr2[j]){
                arr[k++]=arr1[i++];
            }else{
                arr[k++]=arr2[j++];
            }
        }
        while(i<arr1.length){
            arr[k++]=arr1[i++];
        }
        while(j<arr2.length){
            arr[k++]=arr2[j++];
        }
        return arr;
    }






    public static int partition2(int[] arr,int i,int j){
        int tmp=arr[i];
        while(i<j){
            while(i<j&&arr[j]>=tmp){
                j--;
            }
            arr[i]=arr[j];
            while(i<j&&arr[i]<=tmp){
                i++;
            }
            arr[j]=arr[i];
        }
        arr[i]=tmp;
        return i;
    }
    public static void quickSort3(int[] arr){
        int left=0;
        int right=arr.length-1;
        int pivot=partition2(arr,left,right);
        Stack<Integer> stack=new Stack<>();
        if(pivot>left+1){
            stack.add(left);
            stack.add(pivot-1);
        }
        if(pivot<right-1){
            stack.add(pivot+1);
            stack.add(right);
        }
        while(!stack.isEmpty()){
            right=stack.pop();
            left=stack.pop();
            pivot=partition(arr,left,right);
            if(pivot>left+1){
                stack.add(left);
                stack.add(pivot-1);
            }
            if (pivot < right - 1) {
                stack.add(pivot+1);
                stack.add(right);
            }
        }
    }






    public static void swap(int[] arr,int i,int j){
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }
    public static int partition1(int[] arr,int start,int end){
        int i=start;
        int j=end;
        int tmp=arr[i];
        while(i<j){
            while(i<j&&arr[j]>=tmp){
                j--;
            }
            while(i<j&&arr[i]<=tmp){
                i++;
            }
            swap(arr,i,j);
        }
        swap(arr,i,start);
        return start;
    }
    public static void quick1(int[] arr,int left,int right){
        if(left>=right){
            return;
        }
        int pivot=partition1(arr,left,right);
        quick1(arr,left,pivot-1);
        quick1(arr,pivot+1,right);
    }
    public static void quickSort1(int[] arr){
        quick1(arr,0,arr.length-1);
    }






    public static int partition(int[] arr,int start,int end){
        int tmp=arr[start];
        while(start<end){
            while(start<end&&arr[end]>=tmp){
                end--;
            }
            arr[start]=arr[end];
            while(start<end&&arr[start]<=tmp){
                start++;
            }
            arr[end]=arr[start];
        }
        arr[start]=tmp;
        return start;
    }
    public static void quick(int[] arr,int left,int right){
        if(left>=right){
            return;
        }
        int pivot=partition(arr,left,right);
        quick(arr,left,pivot-1);
        quick(arr,pivot+1,right);
    }
    public static void quickSort(int[] arr){
        quick(arr,0,arr.length-1);
    }








    public static void mySort(int[] arr){
        for(int i=0;i<arr.length-1;i++){
            boolean bool=true;
            for(int j=0;j<arr.length-i-1;j++){
                if(arr[j]>arr[j+1]){
                    bool=false;
                    int tmp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=tmp;
                }
            }
            if(bool){
                break;
            }
        }
    }





    public static void shiftDown1(int[] arr,int parent,int len){
        int child=parent*2+1;
        while(child<len){
            if(child+1<len&&arr[child]<arr[child+1]){
                child++;
            }
            if(arr[child]>arr[parent]){
                int tmp=arr[child];
                arr[child]=arr[parent];
                arr[parent]=tmp;
            }else{
                break;
            }
        }
    }
    public static void mySort3(int[] arr){
        for(int i=(arr.length-1)/2;i>=0;i--){
            shiftDown1(arr,i,arr.length);
        }
    }
    public static void heapSort1(int[] arr){
        mySort3(arr);
        int end=arr.length-1;
        while(end>0){
            int tmp=arr[end];
            arr[end]=arr[0];
            arr[0]=tmp;
            shiftDown1(arr,0,end);
            end--;
        }
    }




    public void shiftDown(int[] arr,int parent,int len){
        int child=parent*2+1;
        while(child<len){
            if(child+1<len&&arr[child]<arr[child+1]){
                child++;
            }
            if(arr[child]>arr[parent]){
                int tmp=arr[child];
                arr[child]=arr[parent];
                arr[parent]=tmp;
            }else{
                break;
            }
        }
    }
    public void mySort2(int[] arr){
        for(int i=(arr.length-1)/2;i>=0;i--){
            shiftDown(arr,i,arr.length);
        }
    }
    public void heapSort(int[] arr){
        mySort2(arr);
        int end=arr.length-1;
        while(end>0){
            int tmp=arr[0];
            arr[0]=arr[end];
            arr[end]=tmp;
            shiftDown(arr,0,end);
            end--;
        }
    }






    public void mySort1(int[] arr){
        for(int i=0;i<arr.length-1;i++){
            for(int j=i+1;j<arr.length;j++){
                if(arr[i]>arr[j]){
                    int tmp=arr[i];
                    arr[i]=arr[j];
                    arr[j]=tmp;
                }
            }
        }
    }
}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
class Solution {
    public int[] plusOne(int[] digits) {
        for(int i=digits.length-1;i>=0;i--){
            if(digits[i]!=9){
                digits[i]++;
                for(int j=i+1;j<digits.length;j++){
                    digits[j]=0;
                }
                return digits;
            }
        }
        digits=new int[digits.length+1];
        digits[0]=1;
        return digits;
    }







    public boolean verifyPostorders(int[] postorder,int start,int end){
        if(start>=end){
            return true;
        }
        int i=start;
        while(postorder[i]<postorder[end]){
            i++;
        }
        int m=i;
        while(postorder[i]>postorder[end]){
            i++;
        }
        return i==end&&verifyPostorders(postorder,start,m-1)&&verifyPostorders(postorder,m,end-1);
    }
    public boolean verifyPostorder(int[] postorder) {
        return verifyPostorders(postorder,0,postorder.length-1);
    }










    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list=new ArrayList<>();
        if(root!=null){
            Queue<TreeNode> queue=new ArrayDeque<>();
            queue.add(root);
            while(!queue.isEmpty()){
                int size=queue.size();
                List<Integer> ret=new ArrayList<>();
                for(int i=0;i<size;i++){
                    TreeNode tmp=queue.poll();
                    ret.add(tmp.val);
                    if(tmp.left!=null){
                        queue.add(tmp.left);
                    }
                    if(tmp.right!=null){
                        queue.add(tmp.right);
                    }
                }
                list.add(ret);
            }
        }
        return list;
    }









    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if(pushed==null||popped==null){
            return false;
        }
        Stack<Integer> stack=new Stack<>();
        int j=0;
        for(int i=0;i<pushed.length;i++){
            stack.add(pushed[i]);
            while(!stack.isEmpty()&&stack.peek()==popped[j]){
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }

}